package leetcode.editor.cn.q1_300.q100;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author qidi
 * @date 2022-01-18 13:38:18
 */
class Q0149_MaxPointsOnALine {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int maxPoints(int[][] points) {
            int n = points.length;
            if (n <= 2) return n;

            int ans = 2;
            Map<Integer, List<Integer>> map = new HashMap<>();
            for (int i = 0; i < n - 1; i++) {
                for (int j = i + 1; j < n; j++) {
                    int count = 2;
                    for (int k = j + 1; k < n; k++) {
                        if (
                                (points[j][0] - points[i][0]) * (points[k][1] - points[j][1]) == (points[j][1] - points[i][1]) * (points[k][0] - points[j][0])
                        ) {
                            count++;
                        }
                    }
                    ans = Math.max(count, ans);
                }
            }
            return ans;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0149_MaxPointsOnALine().new Solution();
        System.out.println(solution.maxPoints(new int[][]{
                {1, 1}, {2, 2}, {3, 3}
        }));
        System.out.println(solution.maxPoints(new int[][]{
                {1, 1}, {3, 2}, {5, 3}, {4, 1}, {2, 3}, {1, 4}
        }));
    }
}